#include <iostream>

using namespace std;

class sortArr
{
    public:
        // 插入排序
        void insertionSort();
        // 选择排序
        void selectSort();
        // 冒泡排序
        void bulbSort();
        // 希尔排序
        void shellSort();
        // 计数排序 - 适用于范围小的数组
        void counterSort();
        // 快速排序
        void quickSort(int array[],int begin,int end);
        int* quickSortMain();
        // 堆排序
        void heapify(int array[],int n,int i);
        void heapSort();
        // 归并排序
        void mergSort();
        void msort(int[],int[],int ,int);
        void merge(int*,int*,int,int,int);


        void showArray(int array[]);
        int* getArray()
        {
            return arr;
        }

    private:
        int arr[8]={90,12,14,1,4,46,32,6};
        int arr2[10]={5,5,4,4,1,8,5,3,4,9};
        int length=sizeof(arr)/sizeof(int);
};

void sortArr::showArray(int array[])
{
    for(int i=0;i<length;i++)
    {
        cout<<array[i]<<' ';
    }
    cout<<endl;
}

void sortArr::insertionSort()
{
    int *temparr=new int[this->length];
    for(int i=0;i<this->length;i++)
    {
        temparr[i]=arr[i];
    }
    for(int i=1;i<this->length;i++)
    {
        int j=i-1;
        int temp=temparr[i];
        while(j>=0)
        {
            if(temparr[j]<temp)
            {
                break;
            }
            temparr[j+1]=temparr[j];
            j--;
        }
        temparr[j+1]=temp;
        // this->showArray(temparr);

    }
    this->showArray(temparr);
}

void sortArr::selectSort()
{
    int *temparr=new int[length];
    for(int i=0;i<this->length;i++)
    {
        temparr[i]=this->arr[i];
    }
    for(int i=0;i<this->length-1;i++)
    {
        int temp=temparr[i],minValue=temparr[i],counter=i;
        for(int j=i+1;j<length;j++)
        {
            if(minValue>temparr[j])
            {
                minValue=temparr[j];
                counter=j;
            }
        }
        temparr[i]=minValue;
        temparr[counter]=temp;
    }
    this->showArray(temparr);
}

void sortArr::bulbSort()
{
    int *temparr=new int[length];
    for(int i=0;i<this->length;i++)
    {
        temparr[i]=arr[i];
    }
    for(int i=this->length-1;i>=0;i--)
    {
        for(int j=0;j<i;j++)
        {
            if(temparr[j]>temparr[j+1])
            {
                int temp=temparr[j];
                temparr[j]=temparr[j+1];
                temparr[j+1]=temp;
            }
        }
    }
    this->showArray(temparr);
}

void sortArr::shellSort()
{
    int *temparr=new int[length];
    for(int i=0;i<this->length;i++)
    {
        temparr[i]=arr[i];
    }
    int inc;
    for(int i=(length-1)/2;i>0;i/=2)
    {
        // 每一趟采用插入排序，分开来做
        for(int j=length-1;j>=0;j--)
        {
            int key=temparr[j];
            int k;
            for( k=j;k-i>0;k-=i)
            {
                if(temparr[k]>temparr[k-i])
                {
                    temparr[k]=temparr[k-i];
                }
                else
                {
                    break;
                }

            }
            temparr[k]=key;
            this->showArray(temparr);
        }
    }
    this->showArray(temparr);
}

void sortArr::counterSort()
{
    const int tempLength=10;
    int tempArr[10];
    for(int i=0;i<tempLength;i++)
    {
        tempArr[i]=this->arr2[i];
    }
    // 计数数组
    int countArr[tempLength+1]={0};
    for(int i=0;i<tempLength;i++)
    {
        countArr[tempArr[i]]++;
    }

    // 累计数组
    int cumulativeArray[tempLength+1]={0};
    cumulativeArray[0]=countArr[0];
    for(int i=1;i<tempLength+1;i++)
    {
        cumulativeArray[i]=cumulativeArray[i-1]+countArr[i];
    }
    // 最终结果
    int outputArray[tempLength+1]={0};
    for(int i=0;i<tempLength;i++)
    {
        outputArray[cumulativeArray[tempArr[i]]]=tempArr[i];
        cumulativeArray[tempArr[i]]--;
    }
    this->length=tempLength;

    this->showArray(outputArray);
    this->length=8;
}

int* sortArr::quickSortMain()
{
    int *tempArr=new int[8];
    for(int i=0;i<this->length;i++)
    {
        tempArr[i]=this->arr[i];
    }
    quickSort(tempArr,0,length-1);
    return tempArr;
}

void sortArr::quickSort(int array[],int begin,int end)
{
    if(begin>end)
    {
        return ;
    }
    int temp=array[begin];
    int i=begin;
    int j=end;
    while(i!=j)
    {
        while(array[j]>=temp && j>i)
        {
            j--;
        }
        while(array[i]<=temp && j>i)
        {
            i++;
        }
        if(j>i)
        {
            int t=array[i];
            array[i]=array[j];
            array[j]=t;
        }
    }
    array[begin]=array[i];
    array[i]=temp;
    quickSort(array,begin,i-1);
    quickSort(array,i+1,end);
}

void sortArr::heapify(int array[],int n,int i)
{
    int largstNode=i;
    int lChild=2*i+1;
    int rChild=2*i+2;

    if(lChild<n && array[lChild]>array[largstNode])
    {
        largstNode=lChild;
    }
    if(rChild<n && array[rChild]>array[largstNode])
    {
        largstNode=rChild;
    }
    // 最大的元素不为当前元素，交换节点继续堆排序
    if(largstNode!=i)
    {
        int tempValue=array[i];
        array[i]=array[largstNode];
        array[largstNode]=tempValue;
        heapify(array,n,largstNode);
    }
}

void sortArr::heapSort()
{
    int *temparr=new int[this->length];
    int resultArr[8];
    for(int i=0;i<this->length;i++)
    {
        temparr[i]=this->arr[i];
    }
    // 建堆
    for(int i=this->length/2-1;i>=0;i--)
    {
        heapify(temparr,this->length,i);
    }
    // 排序
    for(int i=this->length-1;i>0;i--)
    {
        int tempValue=temparr[0];
        temparr[0]=temparr[i];
        temparr[i]=tempValue;
        this->heapify(temparr,i,0);
    }
    this->showArray(temparr);
}

void sortArr::merge(int tempArr[],int helpArr[],int left,int mid,int right)
{
    // 标记左半区第一个未排序的因素
    int lPos=left;
    // 标记右半区第一个未排序的因素
    int rPos=mid+1;
    // 临时数组元素的下标
    int Index=left;
    //合并
    while(lPos<=mid&& rPos<=right)
    {
        if(tempArr[lPos]<tempArr[rPos])
        {
            helpArr[Index]=tempArr[lPos];
            Index++;
            lPos++;
        }
        else
        {
            helpArr[Index]=tempArr[rPos];
            Index++;
            rPos++;  
        }
    }
    // 合并剩余的元素
    while(lPos<=mid)
    {
        helpArr[Index++]=tempArr[lPos++];
    }
    while(rPos<=right)
    {
        helpArr[Index++]=tempArr[rPos++];
    }
    // 将排序之后的得到的数组覆盖原来的数组
    while(left<=right)
    {
        tempArr[left]=helpArr[left];
        left++;
    }
}

void sortArr::msort(int tempArr[],int helpArr[],int left,int right)
{
    if(left<right)
    {
        int mid=(left+right)/2;
        // 递归划分区域
        msort(tempArr,helpArr,left,mid);
        msort(tempArr,helpArr,mid+1,right);
        //合并以及划分的区域
        merge(tempArr,helpArr,left,mid,right);
    }
}

void sortArr::mergSort()
{
    int tempArr[8],helpArr[8];
    for(int i=0;i<this->length;i++)
    {
        tempArr[i]=this->arr[i];
    }
    msort(tempArr,helpArr,0,this->length-1);
    this->showArray(tempArr);
}

int main()
{
    sortArr sortTest;
    sortTest.insertionSort();
    sortTest.selectSort();
    sortTest.bulbSort();
    sortTest.shellSort();
    sortTest.counterSort();
    sortTest.showArray(sortTest.quickSortMain());
    sortTest.heapSort();
    sortTest.mergSort();
}